package cn.edu.zzuli.tree;

import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

public class HuffmanTree {

    //哈夫曼树
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};

        //创建哈夫曼树
        HuffmanNode root = createHuffman(arr);
        preOrder(root);
    }

    //创建哈夫曼树
    private static HuffmanNode createHuffman(int[] arr) {
        //首先转化成list方便操作
        List<HuffmanNode> data = new LinkedList<>();

        for (int i = 0; i < arr.length; i++) {
            data.add(new HuffmanNode(arr[i]));
        }

        while (data.size() > 1) {
            //进行排序（也可以自己手写）
            data = data.stream().sorted((o1, o2) -> o1.val - o2.val).collect(Collectors.toList());

            //去除两个最小的值
            HuffmanNode leftNode = data.get(0);
            HuffmanNode rightNode = data.get(1);

            //生成树
            HuffmanNode parent = new HuffmanNode(leftNode.val + rightNode.val);
            parent.left = leftNode;
            parent.right = rightNode;

            data.remove(leftNode);
            data.remove(rightNode);
            data.add(parent);
        }

        //返回根节点。
        return data.get(0);

    }

    public static void preOrder(HuffmanNode root) {
        //首先输出父节点
        System.out.println(root);
        //判断左节点是否为空
        if (root.left != null) {
            preOrder(root.left);
        }
        if (root.right != null) {
            preOrder(root.right);
        }
    }

}

class HuffmanNode {
    int val;
    HuffmanNode left;
    HuffmanNode right;

    public HuffmanNode(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "HuffmanNode{" +
                "val=" + val +
                '}';
    }
}